package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/5 22:37
 * @Version 1.0
 **/
public class MinimumPathSum {
    int result = Integer.MAX_VALUE;
    int lenx, leny;

    /**
     * 动态规划解法
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        lenx = grid.length;
        leny = grid[0].length;

        for (int i = 1; i < lenx; i++) {
            grid[i][0] += grid[i-1][0];
        }
        for (int i = 1; i < leny; i++) {
            grid[0][i] += grid[0][i-1];
        }
        for (int i = 1; i < lenx; i++) {
            for(int j = 1; j < leny; j++) {
                grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[lenx-1][leny-1];
    }


    public int minPathSum2(int[][] grid) {
        lenx = grid.length;
        leny = grid[0].length;
        getResult(0, 0, 0, grid);
        return result;
    }

    /**
     * 递归解法超时
     * @param x
     * @param y
     * @param sum
     * @param grid
     */
    private void getResult(int x, int y, int sum, int[][] grid) {
        if (x == lenx - 1 && y == leny - 1) {
            if (sum < result) {
                result = sum;
            }
            return;
        }

        if (sum >= result) {
            return;
        }
        if (x + 1 < lenx) {
            getResult(x + 1, y, sum + grid[x + 1][y], grid);
        }
        if (y + 1 < leny) {
            getResult(x, y + 1, sum + grid[x][y + 1], grid);
        }

    }
}